package problems.solved;

import java.util.Scanner;

import problems.Problem;

import utils.Utils;

public class Problem67 extends Problem<Integer> {
	private static final int LOOKAHEAD = 21; // minimum lookahead = 21
	private final int[][] triangle = new int[100][];

	public static void main(String[] args) {
		final Problem67 problem67 = new Problem67();
		problem67.runTimed();
		problem67.printResult(); // 7273
	}
	
	@Override
	public void init() {
		Scanner scanner = Utils.getScannerForFile("triangle.txt");
		int i = 0;
		while(scanner.hasNext()) {
			triangle[i++] = parseArray(scanner.nextLine());
		}
	}
	
	private static int[] parseArray(String line) {
		final int size = line.length()/3 + 1;
		int[] result = new int[size];
		Scanner scanner = new Scanner(line);
		scanner.useDelimiter(" ");
		for (int i = 0; i < size; i++) {
			result[i] = scanner.nextInt();
		}
		return result;
	}

	@Override
	public void run() {
		setResult(maxNext(0, 0, LOOKAHEAD));
	}

	private int maxNext(int x, int y, int lookahead) {
		if (x == 99) {
			return triangle[x][y];
		}
		
		int now = triangle[x][y];

		int maxLeft = lookahead(x+1, y, lookahead);
		int maxRight = lookahead(x+1, y+1, lookahead);
		
		if (maxLeft == maxRight) {
			return now + Math.max(maxNext(x+1, y, LOOKAHEAD), maxNext(x+1, y+1, LOOKAHEAD));
		}
		else if (maxLeft > maxRight) {
			return now + maxNext(x+1, y, LOOKAHEAD);
		}
		else {
			return now + maxNext(x+1, y+1, LOOKAHEAD);
		}
	}

	private int lookahead(int x, int y, int lookahead) {
		if (lookahead == 0 || x == 99) {
			return triangle[x][y];
		}
		return triangle[x][y] + Math.max(lookahead(x+1, y, lookahead-1), lookahead(x+1, y+1, lookahead-1));
	}
}
